package day_7_30;

import java.util.ArrayDeque;
import java.util.Queue;

public class Main1 {
    /**
     * 117. 填充每个节点的下一个右侧节点指针 II
     * https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/submissions/648234014/?envType=study-plan-v2&envId=top-interview-150
     */
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

    /**
     * 时间 O(N)
     * 空间 O(1)
     * @param root
     * @return
     */
    public Node connect(Node root) {
        // 因为只需要知道当前层的节点和下一个层的所有节点值即可，那么既可以减小空间的时候
        // 使用 哨兵位来减少对于空节点的判断
        Node dummy = new Node();
        Node cur = root;
        while(cur != null) {
            dummy.next = null;
            Node nxt = dummy; // 下一层的链表
            while(cur != null) {
                // 遍历当前这一层
                if (cur.left != null) {
                    nxt.next = cur.left;
                    nxt = cur.left;
                }
                if (cur.right != null) {
                    nxt.next = cur.right;
                    nxt = cur.right;
                }
                // 遍历到当前层的下一个节点
                cur= cur.next;
            }
            // 这里的 dummy 连接的是 nxt，这时候nxt已经存放的就是下一层的所有节点了
            cur = dummy.next;
        }
        return root;
    }
    /**
     * 时间 O(N)
     * 空间 O(N)
     * @param root
     * @return
     */
    public Node connect2(Node root) {
        if (root == null) {
            return null;
        }
        // 层序遍历，每一层使用一个指针，将其是next进行连接
        Queue<Node> q = new ArrayDeque<>();
        q.offer(root);
        while(!q.isEmpty()) {
            int n = q.size();
            Node before = null;
            for(int i = 1;i <= n;i++) {
                Node cur = q.poll();
                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
                if (i > 1) {
                    // 说明遍历到一层中的除了第一个节点后面节点，进行使用next连接
                    before.next = cur;
                }
                before = cur;
            }
        }
        return root;
        // 时间: O(N)
        // 空间: O(N)
    }
}
